package com.yiwenup.leetcode.offer_ii;

import java.util.ArrayList;
import java.util.List;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.offer_ii
 * @Author yiwenup
 * @Date 2022-02-19 17:39:09
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/TVdhkn/
 */
public class No079 {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0, new ArrayList<>());
        return res;
    }

    /**
     * 深度优先
     * <p>
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了18.69%的用户
     */
    private void dfs(int[] nums, int idx, List<Integer> list) {
        if (idx == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        dfs(nums, idx + 1, list);

        list.add(nums[idx]);
        dfs(nums, idx + 1, list);
        list.remove(list.size() - 1);
    }

    /**
     * 广度优先
     * <p>
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了20.79%的用户
     */
    private List<List<Integer>> bfs(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());

        for (int num : nums) {
            int size = res.size();
            for (int j = 0; j < size; j++) {
                List<Integer> newLs = new ArrayList<>(res.get(j));
                newLs.add(num);
                res.add(newLs);
            }
        }

        return res;
    }
}
